НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені  ІГОРЯ СІКОРСЬКОГО”                     ЗВІТ з лабораторної роботи №2 з навчальної дисципліни “Програмування складних алгоритмів”             Тема: «Рекурсивні алгоритми» Варіант 18              Мета: Метою лабораторної роботи є набуття практичних навичок з рекурсивними функціям. Теоретична частина Рекурсія — метод визначення класу чи об'єкту через попереднє задання одного чи декількох (зазвичай простих) його базових випадків чи методів, а потім заданням на їхній основі правила побудови класу, який визначається. Іншими словами, рекурсія — часткове визначення об'єкта через себе, визначення об'єкта з використанням раніше визначених. Рекурсія використовується, коли можна виділити самоподібність задачі. Термін «рекурсія» використовується в різних спеціальних галузях знань — від лінгвістики до логіки, але найширше застосування знаходить у математиці та інформатиці. У математиці та інформатиці рекурсія пов'язана з методом визначення функцій: рекурсивно задана функція у своєму визначенні містить себе, зокрема, рекурсивною є функція, задана рекурентною формулою. Таким чином, можна одним виразом дати нескінченний набір способів обчислення функції, визначити безліч об'єктів через саму себе з використанням раніше заданих окремих визначень. З рекурсією тісно пов'язана математична індукція: вона є природним способом доведення властивостей функцій на натуральних числах, рекурсивно заданих через свої менші значення. Завдання до лабораторної роботи: Розробити програми згідно з алгоритмом з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму. / Блок-схема // Оцінка складності Розмір Складність Час виконання без рекурсії Час виконання з рекурсією  10  O(N) 4.1e-05 8.1e-06  100  5.2e-05 2.4e-05  1000  6.6e-05 3.7e-05   Результат роботи / Висновок: Було написано програму, що обчислює рівняння за допомогою методу з рекурсією та без неї, а також визначає час виконання кожного з методів. Програмний код https://replit.com/join/tgnewlunuy-okseniait #include <stdio.h> #include <time.h> #define r 5 double noRecursion(double); double recursion(double, double); int main(void) { clock_t start = clock(), diff; double d, k; printf("r=%d\n", r); printf("Результат обчислень без рекурсії: %.7f\n", noRecursion(1)); /*diff = clock() - start; int msec1 = diff * 1000000 / CLOCKS_PER_SEC; printf("\nЧас виконання: %d мікросекунд \n", msec1%1000);*/ // clock_t start = clock(), diff; printf("Результат обчислень з рекурсією: %.7f\n", recursion(1, 0)); diff = clock() - start; int msec1 = diff * 1000000 / CLOCKS_PER_SEC; printf("\nЧас виконання: %d мікросекунд \n", msec1%1000); return 0; } double noRecursion(double d2){ for(double k=1; k<=r; k++){ double d; d=1/(2*k); d2=d2*d; } return d2; } double recursion(double d, double k){ double d0; k++; if (k==r) return (0.5/r); d0=(1/(2*k))*recursion(d, k); return d0; }